﻿#define _CRT_SECURE_NO_WARNINGS 1

// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

#include <assert.h>

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left),
        right(right) {}
    
};


class Solution
{
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend)
    {
        if (inbegin > inend)
            return nullptr;

        // 前序确定根
        TreeNode* root = new TreeNode(preorder[prei++]);

        // 根分割中序左右⼦区间
        int rooti = inbegin;
        while (rooti <= inend)
        {
            if (inorder[rooti] == root->val)
                break;
            else
                rooti++;
        }

        // 递归左右⼦区间，递归构建左右⼦树
        // [inbegin, rooti-1] rooti [rooti+1, inend]
        root->left = _buildTree(preorder, inorder, prei, inbegin, rooti - 1);
        root->right = _buildTree(preorder, inorder, prei, rooti + 1, inend);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int i = 0;
        TreeNode* root =
            _buildTree(preorder, inorder, i, 0, inorder.size() - 1);

        return root;
    }

    // 前序遍历：根 -> 左 -> 右
    void preorderTraversal(TreeNode* root) 
    {
        if (root == nullptr)
            return;

        cout << root->val << " "; // 访问根节点

        preorderTraversal(root->left); // 递归左子树
        preorderTraversal(root->right); // 递归右子树
    }
};

int main()
{
    vector<int> preorder = { 3, 9, 20, 15, 7 }, inorder = { 9, 3, 15, 20, 7 };

    auto root = Solution().buildTree(preorder, inorder);

    Solution().preorderTraversal(root);
    
    return 0;
}



